package main.leetcode.offer.secondround.from03to50;

import java.util.LinkedList;
import java.util.Queue;

/** 13.机器人的运动范围 */
public class ex13 {
    private int res;
    private int m;
    private int n;

    public static void main(String[] args) {
        //        System.out.println(new ex13().movingCount(2, 3, 1));
        System.out.println(new ex13().movingCount(1, 2, 1));
        System.out.println(new ex13().movingCount(10, 10, 5));
        //    System.out.println(new ex13().compare(12, 101, 5));
    }

    //    public int movingCount(int m, int n, int k) {
    //        boolean[][] isVisited = new boolean[m][n];
    //        res = 0;
    //        this.m = m;
    //        this.n = n;
    //        dfs(0, 0, isVisited, k);
    //        return res;
    //    }

    private void dfs(int i, int j, boolean[][] isVisited, int k) {
        if (i > m - 1 || j > n - 1 || isVisited[i][j] || compare(i, j, k)) {
            return;
        }
        ++res;
        isVisited[i][j] = true;
        dfs(i + 1, j, isVisited, k);
        dfs(i, j + 1, isVisited, k);
    }

    private boolean compare(int i, int j, int k) {
        int sum = 0;
        while (i > 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j > 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum > k;
    }

    // bfs
    public int movingCount(int m, int n, int k) {
        boolean[][] isVisited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {0, 0});
        int[] tmp;
        int x;
        int y;
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            x = tmp[0];
            y = tmp[1];
            if (x > m - 1 || y > n - 1 || isVisited[x][y] || compare(x, y, k)) continue;
            ++res;
            queue.add(new int[] {x + 1, y});
            queue.add(new int[] {x, y + 1});
            isVisited[x][y] = true;
        }
        return res;
    }
}
